package dynamicprogramming.乘积最大子数组;

public class Solution {

    public int maxProduct(int[] nums) {
        int ans = nums[0];
        /**
         * 考虑到nums内元素有正有负，单纯的用f[i]表示以i结尾的最大自序乘积在遇到负数时会被阻断
         * 然而当nums内有两个或以上负数时，因为负负得正，这种阻断会干扰正确答案，所以在遇到负数时
         * 不能单纯的将前面值求前值最大，因为有可能还有下一个负数，所以当遇到负数的时我们需要前面的值越小，自身才会最大
         * 所以有
         * nums[i] < 0
         * f_min[i] = min(f_max[i-1] * nums[i] , nums[i])
         * f_max[i] = min(f_min[i-1] * nums[i], nums[i])
         * nums>=0
         * f_min[i] = min(f_min[i-1] * nums[i], nums[i])
         * f_max[i] = min(f_max[i-1] * nums[i], nums[i])
         */
        int length = nums.length;
        int[] f_min = new int[length];
        f_min[0] = nums[0];
        int[] f_max = new int[length];
        f_max[0] = nums[0];
        for (int i = 1; i < length; i++) {
            if (nums[i] < 0) {
                f_min[i] = Math.min(f_max[i - 1] * nums[i], nums[i]);
                f_max[i] = Math.max(f_min[i - 1] * nums[i], nums[i]);
            } else {
                f_min[i] = Math.min(f_min[i - 1] * nums[i], nums[i]);
                f_max[i] = Math.max(f_max[i - 1] * nums[i], nums[i]);
            }
            ans = Math.max(ans, f_max[i]);

        }
        return ans;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxProduct(new int[]{2, 3, -2, -4}));

    }
}
